/***尚硅谷Java数据结构与java算法                  ***/
/***https://www.bilibili.com/video/BV1E4411H73v***/
/***弗洛伊德算法        P187                   ***/
/***C++ 实现版本    written by Daniel           ***/

#include <vector>
#include <iostream>
#include <memory>

//图类
class mGraph
{
public:
    mGraph() = delete;
    mGraph(int num, std::vector<char> vertexVec, std::vector<std::vector<int>> weightVec) : \
        vertexNum(num), vertexVec(vertexVec), weightVec(weightVec), disVec(weightVec), pre(num, std::vector<int>(num,0))
    {
    }
    mGraph(mGraph &graph) = default;
    mGraph(mGraph &&graph) = default;
    //弗洛伊德算法，求各个节点之间的最短路径
    void floyd()
    {
        //中间节点、起点、终点，三层循环遍历
        size_t count=static_cast<size_t>(vertexNum);
        //k为中间节点
        for (size_t k = 0; k < count; k++)
        {
            //i为起始顶点
            for (size_t i = 0; i < count; i++)
            {
                //j为终止顶点
                for(size_t j=0;j<count;j++){
                    if ((disVec[i][k]+disVec[k][j])<disVec[i][j]){
                        disVec[i][j]=disVec[i][k]+disVec[k][j];
                        pre[i][j]=pre[k][j];
                    }
                }
            }            
        }
        

    }
    //显示对象中储存的各种数据
    void showGraph()
    {
        #define XX(vec)                    \
        for (const auto &item : vec)       \
        {                                  \
            for (const auto &item2 : item) \
            {                              \
                std::cout << item2 << "\t";\
            }\
            std::cout << std::endl;\
        } 
        std::cout<<"weightVec:"<<std::endl;
        XX(weightVec);
        std::cout<<"disVec:"<<std::endl;
        XX(disVec);
        std::cout<<"preVec:"<<std::endl;
        XX(pre);
        #undef XX
    }

private:
int vertexNum;
std::vector<char> vertexVec;
std::vector<std::vector<int>> weightVec;
std::vector<std::vector<int>> disVec;
std::vector<std::vector<int>> pre;
}
;

//测试代码
int main()
{
    int vertexNum = 7;
    std::vector<char> vertexVec({'A', 'B', 'C', 'D', 'E', 'F', 'G'});
    const int N = 65535;
    int arr[vertexNum][vertexNum] =
        {{0, 5, 7, N, N, N, 2},
         {5, 0, N, 9, N, N, 3},
         {7, N, 0, N, 8, N, N},
         {N, 9, N, 0, N, 4, N},
         {N, N, 8, N, 0, 5, 4},
         {N, N, N, 4, 5, 0, 6},
         {2, 3, N, N, 4, 6, 0}};
    std::vector<std::vector<int>> weightVec(vertexNum, std::vector<int>(vertexNum, 0));
    for (int i = 0; i < vertexNum; i++)
    {
        for (int j = 0; j < vertexNum; j++)
        {
            weightVec[i][j] = arr[i][j];
        }
    }
    mGraph *graph = new mGraph(vertexNum, vertexVec, weightVec);
    graph->showGraph();
    graph->floyd();
    std::cout<<"after the floyd!"<<std::endl;
    graph->showGraph();
    if (graph != nullptr)
    {
        delete graph;
        graph = nullptr;
    }
}